package interview.questions.数值的整数次方;

/**
 * 问题：
 * <p>
 * 给定一个double类型的浮点数base和int类型的整数exponent。
 * 求base的exponent次方。
 * <p>
 * 注意：
 * <p>
 * 保证base和exponent不同时为0
 */
public class Power {
    /**
     * 解决思路：
     * 考虑要全面，指数为0或者负数的情况。
     * 直接循环计算
     * <p>
     * <p>
     * 问题1：N次方，要计算N-1次乘法，效率低。还有优化空间，可以考虑降次
     */
    public static double Power1(double base, int exponent) {
        if (base == 0) {
            return 0;
        } else if (exponent == 0) {
            return 1;
        }
        double result = 1;
        Boolean flag = false;
        if (exponent < 0) {
            exponent = -exponent;
            flag = true;
        }
        for (int i = 0; i < exponent; i++) {
            result = result * base;
            // 错误处理
            if (result > Double.MAX_VALUE) {
                System.out.println("超出了double类型的范围");
                return -1;
            }
        }
        if (flag == true) {
            return 1 / result;
        }
        return result;
    }

    /**
     * 解决思路：
     * <p>
     * 参考现成的a的n次方公式，发现分奇偶数
     * <p>
     * 问题1：采用递归，发现会出现栈溢出的情况~~改写为循环？但这样快！
     */
    public static double Power2(double base, int exponent) {
        if (exponent == 0) {
            return 1;
        }
        if (exponent == 1) {
            return base;
        }
        double result = Power2(base, exponent >> 1);
        result *= result;
        // exponent 为奇数
        if ((exponent & 1) == 1) {
            result *= base;
        }
        return result;
    }

    /**
     * 有时间学习下，栈溢出的相关知识
     */
    public static double Power3(double base, int exponent) {
        int i = 1;
        double result = base;
        Boolean flag = false;
        if (exponent < 0) {
            flag = true;
            exponent = -exponent;
        }
        while (i < exponent) {
            result *= result;
            i *= 2;
        }
        if (i - 1 == exponent) {
            // 奇数情况，多乘了一次
            result = result / base;
        }
        if (flag) {
            result = 1.0 / result;
        }
        return result;
    }
}
